package com.ahpu.lyf.binarytree;

public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {

        ThreadedTreeNode root = new ThreadedTreeNode(1, "tom");
        ThreadedTreeNode node2 = new ThreadedTreeNode(3, "jack");
        ThreadedTreeNode node3 = new ThreadedTreeNode(6, "smith");
        ThreadedTreeNode node4 = new ThreadedTreeNode(8, "mary");
        ThreadedTreeNode node5 = new ThreadedTreeNode(10, "king");
        ThreadedTreeNode node6 = new ThreadedTreeNode(14, "dim");

        //手动构建二叉树
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);

        ThreadedBinaryTree threadedBinaryTree=new ThreadedBinaryTree(root);
        threadedBinaryTree.preOrder();
        System.out.println("中序线索化二叉树");
        threadedBinaryTree.infixThreadedBinaryTree();
        //测试10号节点
        ThreadedTreeNode node5Left = node5.getLeft();
        ThreadedTreeNode node5Right = node5.getRight();
        System.out.println("10号节点的前驱是"+node5Left);
        System.out.println("10号节点的后继是"+node5Right);
        System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");
        System.out.println("遍历线索化二叉树");
        threadedBinaryTree.threadedList();
    }
}

class ThreadedBinaryTree {
    private final ThreadedTreeNode root;
    //指向前驱的节点
    private ThreadedTreeNode pre=null;


    public ThreadedBinaryTree(ThreadedTreeNode root) {
        this.root = root;
    }

    public void infixThreadedBinaryTree(){
        this.infixThreadedBinaryTree(root);
    }


    public void threadedList(){
        ThreadedTreeNode node=root;
        while (node!=null){
            //循环的找到leftType ==1的结点,第一个找到就是8结点
            //后面随着遍历而变化,因为当leftType==1时，说明该结点是按照线索化
            // 处理后的有效结点
            while (node.getLeftType()==0){
                node=node.getLeft();
            }
            //打印当前这个节点
            System.out.println(node);
            //如果当前结点的右指针指向的是后继结点,就一直输出
            while (node.getRightType()==1){
                //获取当前节点的后继节点
                node=node.getRight();
                System.out.println(node);
            }
            //替换这个遍历的节点
            node=node.getRight();
        }
    }

    /**
     * 中序线索化二叉树的方法
     * @param node 当前的节点
     */
    private void infixThreadedBinaryTree(ThreadedTreeNode node){
        //如果要处理的node为空，则直接结束
        if (node==null)
            return;
        //先线索化左子树
        infixThreadedBinaryTree(node.getLeft());
        //处理中间节点
        //先处理前驱节点
        //左指针为空则设置前驱节点
        if (node.getLeft()==null){
            //当前节点的左指针指向前驱节点
            node.setLeft(pre);
            //设置当前前驱节点的类型
            node.setLeftType(1);
        }

        //处理后继节点
        //右指针为空则设置后继节点
        if(pre!=null&&pre.getRight()==null){
            //让前驱节点的右指针指向当前节点
            pre.setRight(node);
            //设置后继节点的类型
            pre.setRightType(1);
        }
        //每处理一个节点，就记录当前节点作为下一个节点的前驱节点
        pre=node;

        //再线索化右子树
        infixThreadedBinaryTree(node.getRight());
    }


    /**
     * 前缀遍历
     */
    public void preOrder() {
        if (root != null)
            root.preOrder();
        else
            System.out.println("二叉树为空！");
    }

    /**
     * 中缀遍历
     */
    public void infixOrder() {
        if (root != null)
            root.infixOrder();
        else
            System.out.println("二叉树为空！");
    }

    /**
     * 后缀遍历
     */
    public void suffixOrder() {
        if (root != null)
            root.suffixOrder();
        else
            System.out.println("二叉树为空！");
    }
}



class ThreadedTreeNode {
    private Integer id;
    private String name;
    private ThreadedTreeNode left;
    private ThreadedTreeNode right;
    //说明
    //1.如果leftType == 表示指向的是左子树，如果1则表示指向前驱结点
    //2.如果rightType ==表示指向是右子树，如果1表示指向后继结点
    private int leftType;
    private int rightType;

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    public ThreadedTreeNode(Integer id, String name) {
        this.id = id;
        this.name = name;
    }

    public Integer getId() {
        return id;
    }

    public void setId(Integer id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public ThreadedTreeNode getLeft() {
        return left;
    }

    public void setLeft(ThreadedTreeNode left) {
        this.left = left;
    }

    public ThreadedTreeNode getRight() {
        return right;
    }

    public void setRight(ThreadedTreeNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "ThreadedTreeNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    /**
     * 前缀遍历     根左右
     */
    public void preOrder() {
        //先打印根节点
        System.out.println(this);

        //左节点非空，递归遍历左节点
        if (this.left != null)
            this.left.preOrder();
        //右节点非空，递归遍历右节点
        if (this.right != null)
            this.right.preOrder();
    }

    /**
     * 中缀遍历     左中右
     */
    public void infixOrder() {
        //左节点非空，递归遍历左节点
        if (this.left != null)
            this.left.infixOrder();
        //打印根节点
        System.out.println(this);

        //右节点非空，递归遍历右节点
        if (this.right != null)
            this.right.infixOrder();
    }


    /**
     * 后缀遍历     左右中
     */
    public void suffixOrder() {
        //左节点非空，递归遍历左节点
        if (this.left != null)
            this.left.suffixOrder();
        //右节点非空，递归遍历右节点
        if (this.right != null)
            this.right.suffixOrder();
        //打印根节点
        System.out.println(this);
    }
}
